package com.yuan.leet_note.algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;

/**
 * @ClassName: Lru
 * @Description: TODO
 * @Author MrYuan
 * @Date: 2021/6/28 16:53
 * @Version 1.0
 */
/*设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
        set(key, value)：将记录(key, value)插入该结构
        get(key)：返回key对应的value值
        [要求]
        set和get方法的时间复杂度为O(1)
        某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
        当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。
        若opt=1，接下来两个整数x, y，表示set(x, y)
        若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
        对于每个操作2，输出一个答案*/
public class Lru {
    //    LinkedHashMap,stack结构，先进先出
    public static int[] lru(int[][] operators, int k) {
        Integer rows = operators.length;
        Integer lenght = operators[0].length;
        if (rows == 0 || lenght == 0) {
            return null;
        }
        ArrayList<Integer> list = new ArrayList<>();
        LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
        for (int[] operator : operators) {
            int key = operator[1];
            switch (operator[0]) {
                case 1:
                    int value = operator[2];
                    if (map.size() < k) {
                        map.put(key, value);
                    } else {
                        Iterator<Integer> iterator = map.keySet().iterator();
                        map.remove(iterator.next());
                        map.put(key, value);
                    }
                    break;
                case 2:
                    if (map.containsKey(key)) {
                        Integer val = map.get(key);
                        map.remove(key);
                        map.put(key, val);
                        list.add(val);
                    } else {
                        list.add(-1);
                    }
            }
        }

        int[] results = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            results[i] = list.get(i);
        }
        return results;
    }

    public static void main(String[] args) {
        int[][] ints = new int[][]{{1,1,1},{1,2,2},{1,3,2},{2,1},{1,4,4},{2,2}};
        int[] lru = lru(ints, 3);
        for (int i : lru) {
            System.out.println(i);
        }
    }
}